23 顺序表和单链表的对比分析

顺序表和单链表的对比分析

问题

如何判断某个数据元素是否存在于线性表中？
遗失的操作 - find
- 可以为线性表(List)增加一个查找操作
- int find(const T &e) const;
参数:待查找的数据元素
返回值:
- >=0：数据元素在线性表中第一次出现的位置
  - -1:数据元素不存在

数据元素查找示例

LinkList<int> list;
for(int i=0;i<5;i++)
{
    list.insert(0,i);
}
cout <<list.find(3)<<endl;    //     -->3

编程实验

查找操作

#ifndef LIST_H
#define LIST_H

template<typename T>
class List{
public:
    List() = default;
    virtual bool append(const T &value) = 0;
    virtual bool insert(int index,const T &value) = 0;
    virtual bool remove(int index) = 0;
    virtual bool set(int index,const T &value) = 0;
    virtual bool get(int index,T &value) = 0;
    virtual const T &at(int index) const = 0;
    virtual int find(const T &value)const = 0;
    virtual int length() const = 0;
    virtual void clear() = 0;

protected:
    List(List&) = delete;
    List& operator = (const List&)=delete ;
};

#endif // LIST_H

时间复杂度对比分析

操作	SeqList	LinkList
insert	O(n)	O(n)
remove	O(n)	O(n)
set	O(1)	O(n)
get	O(1)	O(n)
find	O(n)	O(n)
length	O(1)	O(1)
clear	O(1)	O(n)

有趣的问题

顺序表的整体时间复杂度比单链表要低，那么单链表还有使用价值吗？
效率的深度分析
- 实际工程开发中，时间复杂度只是效率的一个参考指标
  - 对于内置基础类型，顺序表和单链表的效率不相上下
  - 对于自定义类类型，顺序表在效率上低于单链表
- 插入和删除
  - 顺序表:涉及大量数据对象的复制操作
  - 单链表:只涉及指针操作，效率与数据对象无关
- 数据访问
  - 顺序表:随机访问,可直接定位数据对象
  - 单链表:顺序访问，必须从头访问数据对象，无法直接定位
工程开发中的选择
- 顺序表
  - 数据元素的类型相对简单，不涉及深拷贝
  - 数据元素相对稳定，访问操作远多于插入和删除操作
- 单链表
  - 数据元素的类型相对复杂，复制操作相对耗时
  - 数据元素不稳定，需要经常插入和删除，访问操作较少

小结

线性表中元素的查找依赖于相等比较操作符(==)
顺序表适用于访问需求量较大的场合(随机访问)
单链表适用于数据元素频繁插入删除的场合(顺序访问)
当数据类型相对简单时，顺序表和单链表的效率不相上下

24 单链表的遍历与优化

单链表的遍历与优化

问题

如何遍历单链表中的每一个数据元素?

当前单链表的遍历方法

LinkList<int> list;
for(int i=0;i<5;i++)    // O(?)   O(n)
{
    list.insert(0,i);
}
for(int i=0;i<list.length();i++)    // O(?)  O(n2)
{
    cout<<list.get(i)<<endl;
}

遗憾的事实
- 不能以线性的时间复杂度完成单链表的遍历
新的需求
- 为单链表提供新的方法，在线性时间内完成遍历
设计思路(游标)
- 在单链表的内部定义一个游标(Node *m_current)
- 遍历开始前将游标指向位置为0的数据元素
- 获取游标指向的数据元素
- 通过结点中的next指针移动游标
提供一组遍历相关的函数，以线性的时间复杂度遍历链表。

函数功能说明
move() 将游标定位到目标位置
next() 移动游标
current() 获取游标所指向的数据元素
end() 游标是否到达尾部(是否为空)

函数	功能说明
move()	将游标定位到目标位置
next()	移动游标
current()	获取游标所指向的数据元素
end()	游标是否到达尾部(是否为空)

编程实验一

单链表的遍历

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include "List.h"
#include <stdexcept>
#include <iostream>

template<typename T>
class LinkedList:public List<T>{
protected:
    class Node;     //此处只做声明
public:
    LinkedList(){

    }

    virtual int length() const{
        return m_length;
    }

    virtual void clear(){
        Node *node = m_header.next;
        while (node !=nullptr) {
            Node *deleteNode = node;
            node = node->next;
            destroy(deleteNode);
            m_length--;
        }
    }


    /**
     * @brief insert
     * @param index [0,m_length)
     * @param value
     * @return
     */
    virtual bool insert(int index,const T &value){
        bool ret = false;
        if((index>=0)&&(index<m_length)){
            auto node = position(index);//定位到Node[index-1]
            Node *newNode = create();
            if(newNode != nullptr){
                newNode->value = value;
                newNode->next = node->next;
                node->next = newNode;
                m_length++;
                ret = true;
            }
        }
        return ret;
    }

    virtual bool append(const T &value){
        bool ret = false;
        Node *node = reinterpret_cast<Node*>(&m_header);
        while (node->next!=nullptr) {
            node =node->next;
        }
        Node *newNode = create();
        if(newNode!=nullptr){
            newNode->value = value;
            node->next = newNode;
            m_length++;
            ret = true;
        }
        return ret;
    }

    virtual bool remove(int index){
        bool ret = false;
        if((index>=0)&&(index<m_length)){
            auto node = position(index);//定位到Node[index-1]
            Node *deleteNode = node->next;
            node->next = deleteNode->next;
            destroy(deleteNode);
            m_length--;
            ret = true;
        }
        return ret;
    }

    virtual bool set(int index,const T &value) {
        bool ret = false;
        if((index>=0)&&(index<m_length)){
            auto node = position(index);//定位到Node[index-1]
            node->next->value=value;
            ret = true;
        }
        return ret;
    }

    virtual bool get(int index,T &value) {
        bool ret = false;
        if((index>=0)&&(index<m_length)){
            auto node = position(index);//定位到Node[index-1]
            value = node->next->value;
            ret = true;
        }
        return ret;
    }

    virtual  const T &at(int index) const {
        if((index>=0)&&(index<m_length)){
            Node *node = reinterpret_cast<Node*>(&m_header);
            for(int i=0;i<index;i++){   //定位到Node[index-1]
                node = node->next;
            }
            return node->next->value;
        } else {
            throw std::out_of_range("Parameter index is out of range...");
        }
    }

    virtual bool move(int index,int step = 1){
        bool ret = false;
        if(step>0){
            if((index>=0)&&(index<m_length)){
                m_current = position(index)->next;
                m_step = step;
                ret = true;
            }
        } else {
            throw std::invalid_argument("Parameter 'step' is must greater than or equal to 1 ...");
        }
        return ret;
    }

    virtual bool end(){
        return (m_current == nullptr);
    }

    virtual bool next(){
        int i=0;
        while((i<m_step)&&(!end())){
            m_current = m_current->next;
            i++;
        }
        return (i==m_step);
    }

    virtual const T& current()const{
        return m_current->value;
    }

    virtual int find(const T &value)const{
        int ret = -1,pos = 0;
        Node* node = reinterpret_cast<Node*>(&m_header);
        while (node->next !=nullptr) {
            if(node->next->value == value){
                ret = pos;
                break;
            } else {
                node = node->next;
                pos++;
            }
        }
        return ret;
    }

    ~LinkedList(){
       this->clear();
    }

protected:
    /**
     * @brief position
     * @param index
     * @return
     * @abstract 定位到Node[index-1]
     */
    Node* position(int index){
        Node *node = reinterpret_cast<Node*>(&m_header);
        for(int i=0;i<index;i++){   //定位到Node[index-1]
            node = node->next;
        }
        return node;
    }

    virtual Node* create(){
        return new Node();
    }

    virtual void destroy(Node *node){
        delete node;
    }

    class Node{
    public:
        T value;
        Node *next = nullptr;
    };

    class {
    public:
        char reserved[sizeof (T)];
        Node *next = nullptr;
    }mutable m_header;

    int m_length = 0;
    Node *m_current = nullptr;
    int m_step = 0;
};

#endif // LINKEDLIST_H

遍历函数原型设计
- bool move(int i,int step = 1);
- bool end();
- T current();
- bool next();

单链表内部的一次封装

virtual Node* create() {
    return new Node();
}
virtual void destroy(Node *pn) {
    delete pn;
}

编程实验(二)

内部的封装

virtual Node* create()
{
    return new Node();
}
virtual void destroy(Node *pn)
{
    delete pn;
}

问题

封装create和destroy函数的意义是什么？

为了后面的静态单链表作准备

小结

单链表的遍历需要在线性时间内完成
在单链表内部定义游标变量，通过游标变量提高效率
遍历相关的成员函数是相互依赖，相互配合的关系
封装结点的申请和删除操作更有利于增强扩展性

23 顺序表和单链表的对比分析

顺序表和单链表的对比分析​

编程实验​

小结​

24 单链表的遍历与优化

单链表的遍历与优化​

编程实验一​

编程实验(二)​

小结​

顺序表和单链表的对比分析

编程实验

小结

单链表的遍历与优化

编程实验一

编程实验(二)

小结